package Java1Test;

import utils.PrintArr;

public class QuickSort {
    public static void main(String[] args) {
        // 初始化待排序数组
//        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
        int[] arr = {5, 2, 3, 1};
        // 调用快速排序方法（初始范围为整个数组）
        quickSort(arr, 0, arr.length - 1);

        // 输出排序结果
        PrintArr.printArr(arr);
    }

    /**
     * 快速排序算法实现
     * @param arr 待排序的数组
     * @param left 当前分区的左边界索引
     * @param right 当前分区的右边界索引
     */
    public static void quickSort(int[] arr, int left, int right) {
        // 定义起始指针
        int start = left;
        // 定义结束指针
        int end = right;

        // 递归终止条件：如果起始指针大于结束指针，说明分区已处理完毕
        if (left >= right) {
            return;
        }

        // 选择基准数（通常选择分区的第一个元素）
        int baseNumber = arr[left];

        // 分区过程：将数组分为两部分，左边部分小于基准数，右边部分大于基准数
        while (start != end) {
            /*基准数在前面, 所以
            一定是先移动右指针找小的数, 因为需要把找到的数交换到前面去
            如果先移动左指针先找大的数, 就会把大的数交换到前面去*/
            // 从右向左找第一个小于基准数的元素
            while (end > start && arr[end] >= baseNumber) {
                end--;//2
            }

            // 从左向右找第一个大于基准数的元素
            while (end > start && arr[start] <= baseNumber) {
                start++;//1//2
            }

            // 交换这两个元素
            if (start < end) {
                int temp = arr[start];
                arr[start] = arr[end];
                arr[end] = temp;
            }
        }

        // 基准数归位：将基准数放到正确的位置（start/end指针处）
        int temp = arr[left];
        arr[left] = arr[start];
        arr[start] = temp;

        // 递归排序左子分区（基准数左边）
        quickSort(arr, left, start - 1);
        // 递归排序右子分区（基准数右边）
        quickSort(arr, start + 1, right);
    }
}